package yz.com.cn.sort.core;

import lombok.Data;

/**
 * 快排算法
 *
 * @author zhoujian
 */
@Data
public class QuickSort<T extends Comparable> {
    private T[] arr;

    public void sort() {
        this.sort(0, 0, this.arr.length - 1);
    }

    private void sort(int mid, int start, int end) {
        if (start > end) {
            return;
        }
        int begin = start;
        int last = end;
        T targetT = arr[mid];
        while (begin != last) {
            while (arr[begin].compareTo(targetT) >= 0 && begin < last) {
                begin++;
            }
            while (arr[last].compareTo(targetT) <= 0 && begin < last) {
                last--;
            }
            if (begin < last) {
                swap(begin, last);
            }
        }
        arr[mid] = arr[begin];
        arr[begin] = targetT;
        sort(start, start, begin - 1);
        sort(begin, begin, end);
    }

    private void swap(int x, int y) {
        T tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}
